package com.wtgroup.demo.leetcode.q046_全排列;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;

/**
 * LC 方式, 原地
 */
public class Q046_LC {

    /*
    * 字典顺序性无法保证. [1,2,3], 321后才是312
    * */

    public List<List<Integer>> permute(int[] nums) {
        ArrayList<Integer> integers = new ArrayList<>(nums.length);
        for (int num : nums) {
            integers.add(num);
        }
        List<List<Integer>> vessel = new ArrayList<>();
        func(integers, 0, vessel);

        return vessel;
    }

    private void func(List<Integer> nums, int first, List<List<Integer>> vessel) {
        // first 达到最后一位时, 收集结果, 退出
        if (first == nums.size() - 1) {
            // copy
            vessel.add(new ArrayList<>(nums));
            return;
        }

        HashSet<Integer> mark = new HashSet<>();
        for (int i = first; i < nums.size(); i++) {
            Collections.swap(nums, first, i);
            func(nums, first+1, vessel);
            // 逆操作, 状态重置
            Collections.swap(nums, first, i);
        }
    }


    // // 复制内容, to list
    // private List<Integer> toList(int[] nums) {
    //     ArrayList<Integer> integers = new ArrayList<>(nums.length);
    //     for (int num : nums) {
    //         integers.add(num);
    //     }
    //     return integers;
    // }


}
